147 - Dollars/147.cpp

   1 //147 - Dollars [UVa Online Judge]
   2 //Andrés Mejía-Posada [http://blogaritmo.factorcomun.org]
   3 #include <stdio.h>
   4
   5 #define MAX 30000
   6
   7 unsigned long long dp[2][MAX+1];
   8 //dp[i][j] = numero de maneras en que puedo formar j pesos usando las primeras i monedas
   9 //(Tiene un truco: solo necesitamos la fila anterior así que no es necesario construir toda
  10 //la tabla si no sólo dos filas)
  11 int m[] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};
  12
  13 int main(){
  14   dp[0][0] = dp[1][0] = 1LL;
  15   for (int i=0; i<11; ++i){
  16     for (int a=1; a<=MAX; ++a){
  17       dp[i%2][a] = 0;
  18       if (i > 0){
  19         dp[i%2][a] += dp[(i+1)%2][a];
  20       }
  21       if (a - m[i] >= 0){
  22         dp[i%2][a] += dp[i%2][a - m[i]];
  23       }
  24     }
  25   }
  26
  27   int c, d, amount;
  28   while (scanf("%d.%d", &d, &c) == 2 && (d+c)){
  29     amount = d*100 + c;
  30     printf("%3d.%.2d%17llu\n", d, c, dp[10%2][amount]);
  31   }
  32   return 0;
  33 }
  34